package sorting;

import java.util.Arrays;

import util.ArrayUtil;
import util.MathUtil;

public class QuickSort {
	public static void sort(float[] numbers, int l, int r)
	{
		if(l >= r) return;

		if(r - l > 1)
			ArrayUtil.each(numbers, r, MathUtil.random(l, r));

		int pivotIndex = partition(numbers, l, r);

		sort(numbers, l, pivotIndex - 1);
		sort(numbers, pivotIndex + 1, r);
	}
	
	private static int partition(float[] numbers, int l, int r)
	{
		float pivotValue = numbers[r];
		int pivotIndex = l;
		for(int i = l; i <= r - 1; i ++)
		{
			if(numbers[i] <= pivotValue)
			{
				ArrayUtil.each(numbers, i, pivotIndex);
				pivotIndex ++;
			}
		}

		ArrayUtil.each(numbers, r, pivotIndex);
		
		return pivotIndex;
	}
	
	public static void main(String[] args) {
		float[] numbers = {1, 4, 2, 7, 8, 3, 5, 6, 10, 9, 10, 8, 3};
		sort(numbers, 0, numbers.length - 1);
		
		System.out.println(Arrays.toString(numbers));
	}
}
